package likou.offer;

import java.util.HashSet;
import java.util.Set;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/7/31  20:45
 */
public class _12 {
    public static void main(String[] args) {
        System.out.println(exist2(new char[][]{{'1','2','3','4'},{'5','6','7','8'},{'9','0','1','2'}},"1234821765"));
    }

    private char[][] board;
    private char[] words;
    private boolean[][] passed;
    private int len;
    public boolean exist(char[][] board, String word) {
        if(word == null || word.isEmpty() || word.equals("")) {
            return false;
        }
        if(board.length*board[0].length < word.length()) {
            return false;
        }
        this.board = board;
        this.len = board[0].length;
        this.words = word.toCharArray();
        this.passed = new boolean[board.length][len];
        for(int i = 0; i < board.length; ++i){
            for(int j = 0; j < board[0].length; ++j){
                if(board[i][j] == words[0]){
                    if(hasNextRoad(i,j,1)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private boolean hasNextRoad(int x, int y, int i){
        passed[x][y] = true;
        if(i >= words.length) {
            return true;
        }
        if(x+1<board.length && words[i] == board[x+1][y] && !passed[x+1][y]){
            if(i == words.length-1 || hasNextRoad(x+1,y,i+1)) {
                return true;
            }
        }
        if(y+1<board[0].length && words[i] == board[x][y+1] && !passed[x][y+1]){
            if(i == words.length-1 || hasNextRoad(x,y+1,i+1)) {
                return true;
            }
        }
        if(x>0 && words[i] == board[x-1][y] && !passed[x-1][y]){
            if(i == words.length-1 || hasNextRoad(x-1,y,i+1)) {
                return true;
            }
        }
        if(y>0 && words[i] == board[x][y-1] && !passed[x][y-1]){
            if(i == words.length-1 || hasNextRoad(x,y-1,i+1)) {
                return true;
            }
        }
        passed[x][y] = false;
        return false;
    }


    public static boolean exist2(char[][] board, String word) {
//        Set<Integer> set = new HashSet<>();//board[0][0]*1000+board[0][1];
        char[] chars = word.toCharArray();
        for (int i=0;i<board.length;i++){
            for (char j:board[i]){
                System.out.print(j+" ");
            }
            System.out.println();
        }
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                boolean nowP = false;
                if(chars[0]==board[i][j]){
                    nowP = search(board,chars,0,i*1000+j,new HashSet<Integer>());
                    if(nowP){
                        return nowP;
                    }
                }
//                System.out.print(board[i][j]+" ");
            }
//            System.out.println();
        }
        return false;
    }
    public static boolean search(char[][] board,char[] word,int nowW,int nowI,Set<Integer> nowSet){
        if(nowW==word.length){
            return true;
        }
        int i = nowI/1000;
        int j = nowI%1000;
        if(i>=board.length||i<0||j>=board[0].length||j<0||nowSet.contains(nowI)||word[nowW]!=board[i][j]){
            return false;
        }
        nowSet.add(nowI);
        //上下左右
        System.out.println(board[i][j]+"   "+word[nowW]);
        return search(board,word,nowW+1,nowI-1000,nowSet) || search(board,word,nowW+1,nowI+1000,nowSet) || search(board,word,nowW+1,nowI-1,nowSet) || search(board,word,nowW+1,nowI+1,nowSet);
    }

}
